package com.peng.leetcode.list;

import java.util.Deque;
import java.util.LinkedList;

/**
 * RotateRight
 * 61. 旋转链表
 * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
 *
 * @author: lupeng6
 * @create: 2021/1/11 14:11
 */
public class RotateRight {

    public static void main(String[] args) {
        ListNode head = BuildListNode.tailInsert(1, 2, 3);
        ListNode newHead = new RotateRight().rotateRight(head, 4);
        PrintListNode.print(newHead);
    }

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        int length = 0;
        ListNode temp = head;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        k = k > length ? k % length : k;

        ListNode newHead = head;
        Deque<ListNode> queue = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            ListNode curr = newHead;
            while (curr != null) {
                queue.offer(curr);
                curr = curr.next;
            }
            newHead = queue.pollLast();
            ListNode newCurr = newHead;
            while (!queue.isEmpty()) {
                newCurr.next = queue.poll();
                newCurr = newCurr.next;
            }
            newCurr.next = null;
        }
        return newHead;
    }


}
